package pers.tz.题目.leetcode.树;

import pers.tz.common.TreeNode;

/**
 * @author irony
 * @date 2024-03-14
 */
public class leetcode_1008_前序遍历构造二叉搜索树 {
// 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
//
//保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
//
//二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
//
//二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
//
// 示例 1：
//输入：preorder = [8,5,1,7,10,12]
//输出：[8,5,10,1,7,null,12]

    public static void main(String[] args) {

    }

    // 暴力递归，时间复杂度n^2，可以通过单调栈结构优化到n
    public static TreeNode bstFromPreorder(int[] preorder) {
        return process(preorder, 0, preorder.length);
    }

    private static TreeNode process(int[] preorder, int L, int R) {
        if (L > R) {
            return null;
        }

        TreeNode head = new TreeNode(preorder[L]);

        // 从L + 1开始，一直到R，第一个大于L的数，就是左右孩子的边界
        int big = L + 1;
        for (; big <= R; big++) {
            if (preorder[big] > preorder[L]) {
                break;
            }
        }

        head.left = process(preorder, L + 1, big - 1);
        head.right = process(preorder, big, R);

        return head;
    }
}
